1. Field of the Invention
This invention relates to digital maps of the type for displaying road or pathway information, and more particularly toward a method for determining barrier crossing schedules, crossing times and/or locations for convoyed objects such as motor vehicles transported by ferry boat.
2. Related Art
Personal navigation devices utilize digital maps combined with accurate positioning data from GPS or other data streams. Digital maps can also be accessed by personal computers, mobile devices, and other systems. These devices have been developed for many applications, such as navigation assistance for automobile drivers. The effectiveness of these navigation systems is inherently dependent upon the accuracy of digital maps stored in its memory or otherwise accessed through a suitable database connection such as wireless signal, cable, telephone line, etc.
The navigation system 10 shown in FIG. 1 includes a display screen 12 portraying a portion of a stored digital map as a network of roads 14. A traveler having access to a GPS-enabled navigation device 10 may then be generally located on the digital map close to or with regard to a particular road 14 or segment thereof. Some GPS-enabled navigation devices 10, like several models manufactured by TomTom NV (www.tomtom.com), may also be configured as probes to passively generate geo-position measurement points at regular (or sometimes irregular) intervals. These recordings are sometimes referred to as trajectory data and comprise a sequence of geo-coded positions recorded at intervals of, for example, two seconds. Of course, other suitable devices may be used to generate trajectory data including, for example, handheld devices, mobile phones, and the like. Thus, trajectory data may be described as a set of information about the movement of a vehicle (or a person carrying a probe) which contains time-stamped geographic locations (xyz coordinates) and possibly also metadata (vehicle speed, receiver type, vehicle type, etc.).
It is known to take collections of probe measurements for the purpose of incrementally creating and/or updating digital maps. The trajectory data thus produced can be transmitted either on-the-fly or subsequently to a collection service or other map data analysis service via wireless (e.g., cellular) transmission, via internet uploads, or by other convenient methods. Internet uploads may be synchronized to occur in conjunction with digital map updates which navigation device users might obtain as a service. From the collection of trajectory data, road geometries can be inferred and other features and attributes derived by appropriate analytical methods.
A typical collection of trajectory data from a plurality of probes traversing a particular section of a digital map over an extended period of time may contain billions of discrete data points, each geo-coded and time stamped. Probe traces collected over time can be grouped or bundled according to those which match to a common area of the digital map and then overlaid for interpretation by map database editors. Editors use various mathematic and statistical techniques to determine or infer road geometries, compute speed profiles, acceleration profiles, direction of travel, altitude, detect changes in road networks, to compare two road networks, and many other specifications.
Digital map providers continuously strive to improve and update their maps. Inaccurate data, for example, may be unsuitable to compute optimal routes in response to a navigation query, or to provide other reliable information to a traveler. Inaccurate or incomplete information contained in a digital map can result in poor or erroneous navigation instructions and lead to undesirable navigation decisions.
Navigation decisions must take into account natural features of the landscape which present barriers to travel. For example, a river represents a constraint to vehicular travel, as well as to pedestrian and bicycle travel. Typically, a river may be crossed only with the aid of a ferry, bridge or tunnel. The existence or nonexistence of a bridge, ferry or tunnel constitutes an important detail to be recorded in a digital map. Likewise, the average speed over which vehicles have historically crossed a barrier is also an important detail for digital maps.
In the case of some barrier features, which include not only water barriers but also railroad crossings and many other barrier types, it may be common to congregate vehicles or other movable objects and then periodically transport them in convoy across the barrier to the other side. For motor vehicles crossing a water barrier, a ferry boat may transport a group of motor vehicles across the water barrier on a fairly predictable time schedule. Other barrier crossing scenarios will be recognizable by those of skill in the art where vehicles or other objects are moved in convoy across the barrier in a regular recurring manner.
Detecting barrier crossing locations, such as ferry crossings, by simply matching trajectories to a preexisting water map or digital road map is not effective when the digital map does not recognize a ferry crossing in the first place. It is likewise not effective when the digital map (e.g., the water map) is not sufficiently accurate. Techniques have been proposed for detecting groups of moving objects and trajectories using computationally expensive methods that cluster large numbers of trajectories based on distance measures. For example, one such method is proposed in the work “Discovery of Convoys in Trajectory Databases” by H. Jeung, et al., Proceedings of the VLDB Endowment, Volume I, Issue 1 (August 2008), Session: Spatial and Motion Data, pages 1068-1080 (ISSN: 2150-8097). Such methods, however, are shown to be ineffective at finding convoys—that is of finding groups of objects that have moved together for a period of time. Furthermore, the techniques available in the prior art do not exploit the repetitive day-to-day nature of certain types of barrier crossings such as ferry boats and other controlled crossing locations so as to detect these well defined and perhaps least complex types of convoys and then to extrapolate departure timetables and crossing frequencies.
Accordingly, there is a need in the art to mine historic trajectory data to identify certain types of barrier crossings such as ferry boats and the like, wherein conveyed objects (such as vehicles) are periodically and predictably escorted across a barrier.